{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Painting the Walls"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: paintWalls"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #给墙壁刷油漆"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个长度为 <code>n</code>&nbsp;下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>cost</code> 和&nbsp;<code>time</code>&nbsp;，分别表示给&nbsp;<code>n</code>&nbsp;堵不同的墙刷油漆需要的开销和时间。你有两名油漆匠：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>一位需要 <strong>付费</strong>&nbsp;的油漆匠，刷第&nbsp;<code>i</code>&nbsp;堵墙需要花费&nbsp;<code>time[i]</code>&nbsp;单位的时间，开销为&nbsp;<code>cost[i]</code>&nbsp;单位的钱。</li>\n",
    "\t<li>一位 <strong>免费</strong>&nbsp;的油漆匠，刷 <strong>任意</strong>&nbsp;一堵墙的时间为&nbsp;<code>1</code>&nbsp;单位，开销为&nbsp;<code>0</code>&nbsp;。但是必须在付费油漆匠&nbsp;<strong>工作</strong>&nbsp;时，免费油漆匠才会工作。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回刷完 <code>n</code>&nbsp;堵墙最少开销为多少。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>cost = [1,2,3,2], time = [1,2,3,2]\n",
    "<b>输出：</b>3\n",
    "<strong>解释：</strong>下标为 0 和 1 的墙由付费油漆匠来刷，需要 3 单位时间。同时，免费油漆匠刷下标为 2 和 3 的墙，需要 2 单位时间，开销为 0 。总开销为 1 + 2 = 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>cost = [2,3,4,2], time = [1,1,1,1]\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>下标为 0 和 3 的墙由付费油漆匠来刷，需要 2 单位时间。同时，免费油漆匠刷下标为 1 和 2 的墙，需要 2 单位时间，开销为 0 。总开销为 2 + 2 = 4 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= cost.length &lt;= 500</code></li>\n",
    "\t<li><code>cost.length == time.length</code></li>\n",
    "\t<li><code>1 &lt;= cost[i] &lt;= 10<sup>6</sup></code></li>\n",
    "\t<li><code>1 &lt;= time[i] &lt;= 500</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [painting-the-walls](https://leetcode.cn/problems/painting-the-walls/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [painting-the-walls](https://leetcode.cn/problems/painting-the-walls/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,2]\\n[1,2,3,2]', '[2,3,4,2]\\n[1,1,1,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintWalls(self, cost: List[int], time: List[int]) -> int:\n",
    "        N = len(cost)\n",
    "        INF = float('inf')\n",
    "        min_cost = [INF] * (N + 1)\n",
    "        min_cost[0] = 0\n",
    "        for i, (c, t) in enumerate(zip(cost, time)):\n",
    "            for j in range(N -1 , -1, -1):\n",
    "                new_t = min(j + t + 1, N)\n",
    "                if min_cost[new_t] > min_cost[j] + c:\n",
    "                    min_cost[new_t] = min_cost[j] + c\n",
    "        return min_cost[N]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintWalls(self, cost: List[int], time: List[int]) -> int:\n",
    "        inf = float(\"inf\")\n",
    "\n",
    "        n = len(cost)\n",
    "        \n",
    "        dp = [[0]*(n+1) for _ in range(n+1)]\n",
    "        for j in range(1,n+1):\n",
    "            dp[0][j] = inf \n",
    "        \n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,n+1):\n",
    "                vi = time[i-1]+1\n",
    "                cost_i = cost[i-1]\n",
    "                dp[i][j] = min(dp[i-1][max(j-vi,0) ]+cost_i, dp[i-1][j]   )\n",
    "        \n",
    "        return dp[n][n]\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintWalls(self, cost: List[int], time: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        ZERO = 2 * n\n",
    "        dp = [[float(\"inf\")] * (4 * n + 2) for _ in range(n + 1)]\n",
    "        for j in range(ZERO + 1):\n",
    "            dp[0][j] = 0\n",
    "        for i in range(1, n + 1):\n",
    "            t = time[i - 1]\n",
    "            c = cost[i - 1]\n",
    "            for j in range(len(dp[0]) - 2, -1, -1):\n",
    "                dp[i][j] = min(dp[i][j + 1], dp[i - 1][max(j - t, 0)] + c, dp[i - 1][j + 1])\n",
    "        return min(dp[n][ZERO:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintWalls(self, cost: List[int], time: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        DP = [defaultdict(int) for _ in range(n)]\n",
    "        DP[0][-1] = 0\n",
    "        DP[0][min(time[0], n)] = cost[0]\n",
    "        for i in range(1, n):\n",
    "            for j, val in DP[i - 1].items():\n",
    "                k = j - 1\n",
    "                if k not in DP[i]: DP[i][k] = val\n",
    "                else: DP[i][k] = min(DP[i][k], val)\n",
    "                k = min(j + time[i], n)\n",
    "                if k not in DP[i]: DP[i][k] = val + cost[i]\n",
    "                else: DP[i][k] = min(DP[i][k], val + cost[i])\n",
    "        return min([val for key, val in DP[n - 1].items() if key >= 0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintWalls(self, cost: List[int], time: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        l = []\n",
    "        for i in range(n):\n",
    "            l.append([-1]*(n*10))\n",
    "            if i == 0:\n",
    "                l[i][n-1] = 0\n",
    "                l[i][n+time[i]] = cost[i]\n",
    "                continue\n",
    "            for j in range(n*10):\n",
    "                if l[i-1][j] != -1:\n",
    "                    if l[i][j-1] == -1:\n",
    "                        l[i][j-1] = l[i-1][j]\n",
    "                    else:\n",
    "                        l[i][j-1] = min(l[i][j-1],l[i-1][j])\n",
    "                    if j+time[i]>=n*10:\n",
    "                        break\n",
    "                    if l[i][j+time[i]] == -1:\n",
    "                        l[i][j+time[i]] = l[i-1][j] + cost[i]\n",
    "                    else:\n",
    "                        l[i][j+time[i]] = min(l[i][j+time[i]],l[i-1][j] + cost[i])\n",
    "        ans = sum(cost)\n",
    "        # print(l)\n",
    "        for i in l[n-1][n:]:\n",
    "            if i != -1:\n",
    "                ans = min(ans,i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintWalls(self, cost: List[int], time: List[int]) -> int:\n",
    "        n=len(cost)\n",
    "        @cache\n",
    "        def dfs(i,cnt):\n",
    "            if cnt<=0:\n",
    "                return 0\n",
    "            if i<0:\n",
    "                return inf\n",
    "            return min(dfs(i-1,cnt-time[i]-1)+cost[i],dfs(i-1,cnt))\n",
    "        r=dfs(n-1,n)\n",
    "        dfs.cache_clear()\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintWalls(self, cost: List[int], time: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(index: int, left_cnt: int) -> int:\n",
    "            if left_cnt <= 0:\n",
    "                return 0\n",
    "            if index == -1:\n",
    "                return inf\n",
    "            return min(dfs(index - 1, left_cnt), dfs(index - 1, left_cnt - time[index] - 1) + cost[index])\n",
    "        \n",
    "        ans = dfs(n - 1, n)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintWalls(self, cost: List[int], time: List[int]) -> int:\n",
    "        \n",
    "        n = len(cost)\n",
    "        # m = 500000\n",
    "        # f = [[-1]*(m) for _ in range(n)]\n",
    "\n",
    "        # -n ... -1 0 1 ... n\n",
    "        f = [[-1]*(2*n+1) for _ in range(n)]\n",
    "        # for  in range(n):\n",
    "          \n",
    "        # rest = [0]*(n+1)\n",
    "        # for i, t in enumerate(time): rest[i+1] = rest[i] + time[i]\n",
    "        def dfs(i : int, t : int) -> int:\n",
    "            if t > i: \n",
    "                return 0 \n",
    "            if i < 0: # t + rest[i+1] < 0: # i < 0 or t + rest[i+1] < 0:\n",
    "                # f[i][t] = inf\n",
    "                return inf\n",
    "\n",
    "            if f[i][t+n] is not -1:\n",
    "                return f[i][t+n]\n",
    "\n",
    "            f[i][t+n] = min(dfs(i-1, t+time[i]) + cost[i], dfs(i-1, t-1))\n",
    "            return f[i][t+n]\n",
    "        return dfs(n-1, 0)\n",
    "        \n",
    "        \n",
    "        \n",
    "        # rest = [0]*(n+1)\n",
    "        # for i, t in enumerate(time): rest[i+1] = rest[i] + time[i]\n",
    "        # @cache\n",
    "        # def dfs(i : int, t : int) -> int:\n",
    "        #     if t > i: return 0\n",
    "        #     if i < 0 or t + rest[i+1] < 0: return inf\n",
    "        #     return min(dfs(i-1, t+time[i]) + cost[i], dfs(i-1, t-1))\n",
    "        # return dfs(n-1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintWalls(self, cost: List[int], time: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        @cache\n",
    "        def dfs(i:int, t:int):\n",
    "            # print(i,t)\n",
    "            if i == n:\n",
    "                return 0 if t >= 0 else inf\n",
    "            return min(dfs(i+1,min(t+time[i],500)) + cost[i] ,dfs(i+1,t-1))\n",
    "        res = dfs(0,0)\n",
    "        dfs.cache_clear()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintWalls(self, cost: List[int], time: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        \n",
    "        # 到第i面墙，A,B相对耗时情况下，最小消耗，A-B\n",
    "        dp = [defaultdict(lambda :int(1e15)) for _ in range(n+1)]\n",
    "        \n",
    "        # 没A，0小时，消耗0\n",
    "        dp[0][0] = 0\n",
    "        \n",
    "        for i in range(n):\n",
    "            c,t = cost[i],time[i]\n",
    "            \n",
    "            # A不刷\n",
    "            for lt in range(-n,n):\n",
    "                # 差值d要比上一个状态多1\n",
    "                dp[i+1][lt] = dp[i][lt+1]\n",
    "            \n",
    "            # A刷，标准01背包\n",
    "            for lt in range(-n,n+1):\n",
    "                dp[i+1][lt] = min(dp[i+1][lt],dp[i][lt-t]+c)\n",
    "        \n",
    "        res = int(1e15)\n",
    "        for i in range(1,n+1):\n",
    "            # 剩余剩余需要刷的墙都给B刷\n",
    "            rest = n - i\n",
    "            for j in range(rest,n+1):\n",
    "                # print(i,j,dp[i][j])\n",
    "                res = min(res,dp[i][j])\n",
    "        \n",
    "        return res\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintWalls(self, cost: List[int], time: List[int]) -> int:\n",
    "\n",
    "        n = len(cost)\n",
    "        dp = [{} for j in range(n)]\n",
    "        dp[0][time[0]]=cost[0]\n",
    "        dp[0][-1]=0\n",
    "        for i in range(1,n):\n",
    "            for t in dp[i-1]:\n",
    "                dp[i][t+time[i]]=min(dp[i].get(min(n+1,t+time[i]),10**9),dp[i-1][t]+cost[i])\n",
    "                dp[i][t-1]=min(dp[i].get(t-1,10**9),dp[i-1][t])        \n",
    "        return min(dp[-1][ke] for ke in dp[-1] if ke>=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.d = {}\n",
    "        self.acc = [0]\n",
    "\n",
    "    def paintWalls(self, cost: List[int], time: List[int]) -> int:\n",
    "        for ti in time:\n",
    "            self.acc.append(self.acc[-1]+ti)\n",
    "        ret = self.func(0,0,cost,time)\n",
    "        return ret\n",
    "    \n",
    "    def func(self,start,freeleft,cost,time):\n",
    "        lefttime = self.acc[-1] - self.acc[start]\n",
    "        if freeleft + lefttime<0:\n",
    "            return float('inf')\n",
    "        if freeleft >= lefttime:\n",
    "            return 0\n",
    "        \n",
    "        rr = self.d.get((start,freeleft))\n",
    "        if rr!=None:\n",
    "            return rr\n",
    "        \n",
    "        ret1 = cost[start] + self.func(start+1,freeleft+time[start],cost,time)\n",
    "        ret2 = 0 + self.func(start+1,freeleft-1,cost,time)\n",
    "\n",
    "        ret = min(ret1,ret2)\n",
    "\n",
    "        self.d[(start,freeleft)] = ret\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintWalls(self, cost: List[int], time: List[int]) -> int:\n",
    "        @cache\n",
    "        def dp(i, free):\n",
    "            if i == 0:\n",
    "                #print(f'{i=} {free=}')\n",
    "                if 0 <= free <= time[i]:\n",
    "                    return cost[i]\n",
    "                elif free < 0:\n",
    "                    return 0\n",
    "                else:\n",
    "                    return inf\n",
    "            return min(\n",
    "                dp(i-1, max(-n, free-time[i])) + cost[i],\n",
    "                dp(i-1, min(n, free+1)),\n",
    "            )\n",
    "        inf = 0x3f3f3f3f\n",
    "        n = len(cost)\n",
    "        res = min(dp(n-1, free) for free in range(0, n+1))\n",
    "        dp.cache_clear()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintWalls(self, cost: List[int], time: List[int]) -> int:\n",
    "        \n",
    "        # rest 为剩余的时间\n",
    "        # index 墙壁\n",
    "        \n",
    "        # 换成背包问题 -> 时间 + 付钱刷的墙 >= n   ->  time + 1 >= n\n",
    "        # 至少有 大于等于n ，最小化代价\n",
    "        # rest -> n 需要满足的刷墙数\n",
    "        n = len(cost)\n",
    "        dp = [[inf] * n for _ in range(n)]\n",
    "        \n",
    "        @cache\n",
    "        def dfs(index, rest):\n",
    "            if rest <= 0: return 0\n",
    "            if index < 0: return inf\n",
    "            return min(dfs(index - 1, rest - time[index] - 1) + cost[index], dfs(index - 1, rest))\n",
    "        return dfs(n - 1, n)\n",
    "            \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintWalls(self, cost: List[int], time: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        @cache\n",
    "        def getRes(idx, saved):\n",
    "            if idx == n:\n",
    "                if saved < 0: return inf\n",
    "                return 0\n",
    "            return min(getRes(idx+1, saved + time[idx]) + cost[idx], getRes(idx+1, saved-1))\n",
    "        ans = getRes(0, 0)\n",
    "        getRes.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintWalls(self, cost: List[int], time: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        ratio = [[cost[i], time[i]] for i in range(n)]\n",
    "        ratio.sort(key=lambda x: (-x[1] / x[0], -x[1]))\n",
    "        result = float('inf')\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if j >= n - i:\n",
    "                return 0\n",
    "            if i >= n:\n",
    "                return float('inf')\n",
    "            c, t = ratio[i]\n",
    "            return min(dfs(i + 1, j + t) + c, dfs(i + 1, j - 1))\n",
    "\n",
    "                \n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintWalls(self, cost: List[int], time: List[int]) -> int:\n",
    "        n=len(cost)\n",
    "        l=[(cost[i],time[i]) for i in range(n)]\n",
    "        l.sort(key=lambda x:(-x[1],x[0]))\n",
    "        maxv=int(1e9)\n",
    "        nxt=[n]*n\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if l[i][1]==l[i+1][1]:\n",
    "                nxt[i]=nxt[i+1]\n",
    "            else:\n",
    "                nxt[i]=i+1\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def f(p,t):\n",
    "            if t-(n-p)>=0:\n",
    "                return 0\n",
    "            if p==n or t+l[p][1]*(n-p)<0:\n",
    "                return maxv\n",
    "            r=min(l[p][0]+f(p+1,t+l[p][1]),f(nxt[p],t-(nxt[p]-p)))\n",
    "            return r\n",
    "        res=f(0,0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintWalls(self, cost: List[int], time: List[int]) -> int:\n",
    "        \n",
    "        args = sorted(range(len(cost)), key = time.__getitem__)\n",
    "        cost = [cost[i] for i in args]\n",
    "        time = [time[i] for i in args]\n",
    "        \n",
    "        for i in range(len(cost)):\n",
    "            time[i] += 1\n",
    "        \n",
    "        sumt = [0]\n",
    "        for i in time:\n",
    "            sumt.append( sumt[-1]+i)\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dp(mint,i):\n",
    "            if sumt[i] < mint:\n",
    "                return float('inf')\n",
    "            if i==0 or mint<=0:\n",
    "                return 0\n",
    "            \n",
    "            res = min(dp(mint-time[i-1], i-1)+cost[i-1], dp(mint, i-1))\n",
    "            return res\n",
    "        \n",
    "        return dp(len(time), len(time))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintWalls(self, cost: List[int], time: List[int]) -> int:\n",
    "        self.a = list((c/t,c,t) for c,t in zip(cost,time))\n",
    "        self.a.sort()\n",
    "        self.max = sum(cost)\n",
    "        self.runs = 0\n",
    "        return self.dfs(0, 0, 0)\n",
    "        \n",
    "    @lru_cache(1000000)\n",
    "    def dfs(self, i, j, t):\n",
    "        if self.runs>100000:\n",
    "            return self.max\n",
    "        self.runs+=1\n",
    "        if len(self.a)-i+j<=t:\n",
    "            return 0\n",
    "        if i>=len(self.a):\n",
    "            if j>t:\n",
    "                return self.max\n",
    "            return 0\n",
    "        c,t1 = self.a[i][1:]\n",
    "        a = self.dfs(i+1, j, t + t1) + c\n",
    "        b = self.dfs(i+1, j + 1, t)\n",
    "        return min(a,b)\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintWalls(self, cost: List[int], time: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        MAX = sum(cost)\n",
    "\n",
    "        ss = list(zip(cost, time))\n",
    "        ss.sort(key=lambda x: (-x[1], x[0]))\n",
    "\n",
    "        acc = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            acc[i + 1] = acc[i] + ss[i][1]\n",
    "\n",
    "        from functools import cache\n",
    "        @cache\n",
    "        def search(i, t):\n",
    "            if (t + acc[-1] - acc[i]) < 0: return MAX\n",
    "            if t >= (n - i): return 0\n",
    "\n",
    "            # what if paid\n",
    "            a = search(i + 1, t + ss[i][1]) + ss[i][0]\n",
    "            # what if free\n",
    "            b = search(i + 1, t - 1)\n",
    "            ans = min(a, b)\n",
    "            return ans\n",
    "\n",
    "        ans = search(0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintWalls(self, cost: List[int], time: List[int]) -> int:\n",
    "        N = len(cost)\n",
    "        tmp_s = [0]\n",
    "        tmp_s.extend(tmp_s[-1] + t + 1 for t in time)\n",
    "        inf = float('inf')\n",
    "        @cache\n",
    "        def dfs(i, n):\n",
    "            if tmp_s[i+1] < n:\n",
    "                return inf\n",
    "            if n <= 0:\n",
    "                return 0\n",
    "            return min(dfs(i-1, n-time[i]-1) + cost[i], dfs(i-1, n))\n",
    "        return dfs(N-1, N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintWalls(self, cost: List[int], time: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        @cache\n",
    "        def dp(i, time_consumed):\n",
    "            if time_consumed >= n:\n",
    "                return 0\n",
    "            \n",
    "            if i >= n:\n",
    "                return -1\n",
    "            \n",
    "            #paint current\n",
    "            res = dp(i+1, time_consumed + time[i] + 1)\n",
    "            if res == -1:\n",
    "                return -1\n",
    "            \n",
    "            res += cost[i]\n",
    "            #no paint\n",
    "            no_paint_cost = dp(i+1, time_consumed)\n",
    "            if no_paint_cost != -1 and res > no_paint_cost:\n",
    "                res = no_paint_cost\n",
    "            \n",
    "            return res\n",
    "        \n",
    "        return dp(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintWalls(self, cost: List[int], time: List[int]) -> int:\n",
    "        @cache  \n",
    "        def dfs(i:int, j:int) -> int:  \n",
    "            if j<=0: \n",
    "                return 0 \n",
    "            if i<0: \n",
    "                return 9999999999  \n",
    "            return min(dfs(i-1, j-time[i]-1)+cost[i],dfs(i-1, j))\n",
    "        n=len(cost)\n",
    "        return dfs(n-1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintWalls(self, cost: List[int], time: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if j <= 0: return 0\n",
    "            if i < 0: return inf\n",
    "            ans = dfs(i - 1, j - time[i] - 1) + cost[i]\n",
    "            ans = min(ans, dfs(i - 1, j))\n",
    "            return ans\n",
    "        n = len(cost)\n",
    "        return dfs(n - 1, n)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintWalls(self, cost: List[int], time: List[int]) -> int:\n",
    "        # n = len(cost)\n",
    "        # f = [0] + [inf] * n\n",
    "        # for c, t in zip(cost, time):\n",
    "        #     for j in range(n, 0, -1):\n",
    "        #         f[j] = min(f[j], f[max(j-t-1, 0)] + c)\n",
    "        # return f[-1]\n",
    "\n",
    "        @cache  # 记忆化搜索\n",
    "        def dfs(i: int, j: int) -> int:  # j 表示剩余需要的体积\n",
    "            if j <= 0: return 0  # 没有约束：后面什么也不用选了\n",
    "            if i < 0: return inf  # 此时 j>0，但没有物品可选，不合法\n",
    "            return min(dfs(i - 1, j - time[i] - 1) + cost[i], dfs(i - 1, j))\n",
    "        n = len(cost)\n",
    "        return dfs(n - 1, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintWalls(self, cost: List[int], time: List[int]) -> int:\n",
    "        L = len(cost)\n",
    "\n",
    "        @functools.cache\n",
    "        def dp(i,t):\n",
    "            if t<=0: return 0\n",
    "            if i==L: return math.inf\n",
    "\n",
    "            return min(cost[i]+dp(i+1,t-time[i]-1), dp(i+1, t))\n",
    "        \n",
    "        return dp(0,L)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def paintWalls(self, cost: List[int], time: List[int]) -> int:\n",
    "        # time[i]+1 是物品体积，cost[i]是物品价值\n",
    "        # 从n个物品里选出体积和至少为n的物品，价值和最少是多少\n",
    "        n = len(cost)\n",
    "        rec = defaultdict(int)\n",
    "        # 前i个物品，剩余还需要凑出j的体积，此时的最小价值和\n",
    "        def dfs(i,j):\n",
    "            if j<=0:\n",
    "                return 0\n",
    "            if i<0:\n",
    "                return float('inf')\n",
    "            if (i,j) in rec:\n",
    "                return rec[(i,j)]\n",
    "            \n",
    "            res = min(dfs(i-1, j), dfs(i-1, j-time[i]-1)+cost[i])\n",
    "            rec[(i,j)] = res\n",
    "            return res\n",
    "\n",
    "        return dfs(n-1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintWalls(self, cost: List[int], time: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(index: int, left_cnt: int) -> int:\n",
    "            if left_cnt <= 0:\n",
    "                return 0\n",
    "            if index == -1:\n",
    "                return inf\n",
    "            return min(dfs(index - 1, left_cnt), dfs(index - 1, left_cnt - time[index] - 1) + cost[index])\n",
    "        \n",
    "        ans = dfs(n - 1, n)\n",
    "        #dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintWalls(self, cost: List[int], time: List[int]) -> int:\n",
    "        n=len(cost)\n",
    "        @cache\n",
    "        def dfs(idx,now):\n",
    "            if now>=n:\n",
    "                return 0\n",
    "            if idx==n:\n",
    "                return inf\n",
    "            return min(dfs(idx+1,now),dfs(idx+1,now+time[idx]+1)+cost[idx])\n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintWalls(self, cost: List[int], time: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, k) :\n",
    "            if i == n :\n",
    "                return 0 if k >= n else inf\n",
    "            if k >= n :\n",
    "                return 0\n",
    "\n",
    "            ci, ti = cost[i], time[i]\n",
    "            res = inf\n",
    "            return min(res, dfs(i+1, k),  dfs(i+1, k+1+ti) + cost[i])\n",
    "        return dfs(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintWalls(self, cost: List[int], time: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if j >= i + 1:\n",
    "                return 0\n",
    "            if i < 0:\n",
    "                return inf\n",
    "            return min(dfs(i-1,j-1),dfs(i-1,j+time[i])+cost[i])\n",
    "        return dfs(len(cost) - 1,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintWalls(self, cost: List[int], time: List[int]) -> int:\n",
    "        n = len(cost)\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if n - i <= j:\n",
    "                return 0\n",
    "            if i == n:\n",
    "                return 0 if j >= 0 else inf\n",
    "            return min(dfs(i + 1, j - 1), dfs(i + 1, j + time[i]) + cost[i])\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintWalls(self, cost: List[int], time: List[int]) -> int:\n",
    "        # all_dict = {}\n",
    "        n = len(cost)\n",
    "        # for i in range(n):\n",
    "        #     if cost[i] in all_dict:\n",
    "        #         all_dict[cost[i]].append(time[i])\n",
    "        #     else:\n",
    "        #         all_dict[cost[i]] = [time[i]]\n",
    "        # pay_dict = dict(sorted(all_dict.items(), key=lambda x:x[0]))\n",
    "        # pay_list = []\n",
    "        # for k,v in pay_dict.items():\n",
    "        #     v.sort(reverse=True)\n",
    "        #     for i in v:\n",
    "        #         pay_list.append([k, i])\n",
    "        # # return pay_list\n",
    "        \n",
    "        # cost_s = 0\n",
    "        # free_s = n\n",
    "        # all_cost = 0\n",
    "        # while cost_s < free_s:\n",
    "        #     free_s -= pay_list[cost_s][1]\n",
    "        #     all_cost += pay_list[cost_s][0]\n",
    "        #     cost_s += 1\n",
    "        # return all_cost\n",
    "\n",
    "        @cache\n",
    "        # i为刷前n堵墙， j为付费时间-免费时间\n",
    "        def dfs(i, j):\n",
    "            if j > i:\n",
    "                return 0\n",
    "            if i < 0:\n",
    "                return inf\n",
    "            return min(dfs(i-1, j+time[i]) + cost[i], dfs(i-1,j-1))\n",
    "        \n",
    "        return dfs(n-1, 0)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def paintWalls(self, cost: List[int], time: List[int]) -> int:\n",
    "        \n",
    "        L = len(cost)\n",
    "\n",
    "        @functools.cache\n",
    "        def dp(i, tdiff):\n",
    "            if L-i < tdiff:\n",
    "                return 0\n",
    "            if i == L:\n",
    "                return 0 if tdiff>=0 else math.inf\n",
    "\n",
    "            return min(cost[i]+dp(i+1,tdiff+time[i]), dp(i+1, tdiff-1))\n",
    "        \n",
    "        return dp(0, 0)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
